package offer.zixing.chapter06;

import java.util.Stack;

/**
 * 每日温度
 *
 * 输入一个数组，它的每个数字是某天的温度。请计算在每一天需要等几天才会有更高的温度。
 * 例如，如果输入数组[35, 31, 33, 36, 34]，那么输出为[3, 1, 1, 0, 0]。
 * 由于第一天的温度是35，要等3天才会有更高的温度36，因此对应的输出为3。
 * 第四天的温度是36，后面没有更高的温度，它对应的输出是0。
 */
public class Test038 {

    public static void main(String[] args) {
        int[] temperatures = dailyTemperatures(new int[]{35, 31, 33, 36, 34});
        for (int i = 0; i < temperatures.length; i++) {
            System.out.println(temperatures[i]);
        }
    }

    public static int[] dailyTemperatures(int[] temperatures) {
        int[] result = new int[temperatures.length];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < temperatures.length; i++) {
            while (!stack.empty() && temperatures[i] > temperatures[stack.peek()]) {
                int prev = stack.pop();
                result[prev] = i - prev;
            }
            stack.push(i);
        }
        return result;
    }
}
